#include <iostream>
using namespace std;
int book[51],e[51][51],mi=99999,m;
void dfs(int cur,int dis){
	if(dis>mi)return;  
	if(cur==m){
		if(dis<mi)mi=dis;
		return;
	}
	for(int i=1;i<=m;i++){
		if(e[cur][i]!=99999 && book[i]==0){
			book[i]=1;
			dfs(i,dis+e[cur][i]);
			book[i]=0;
		}	}
	return;
	
}
int main() {
	int n,a,b,c,i,j;
	cin>>m>>n;
	for(i=1;i<=m;i++)
		for(j=1;j<=m;j++){
			if(i==j)e[i][j]=0;
			else e[i][j]=99999;
		}
	for(i=1;i<=n;i++){
		cin>>a>>b>>c;
		e[a][b]=c;
	}
	book[1]=1;
	dfs(1,0);
    cout<<mi<<endl;
    return 0;
}

